import random
from typing import List, Dict, Optional, Set, Tuple
from collections import defaultdict, deque


class RecommendationEngine:
    """推荐引擎，基于知识图谱的推荐算法"""

    def __init__(self):
        self.graph = {}  # 邻接表
        self.node_info = {}  # 节点信息

    def build_graph(self, graph_data: Dict, users: List[Dict], posts: List[Dict]):
        """构建图结构"""
        # 重置图
        self.graph = defaultdict(list)
        self.node_info = {}

        # 添加话题节点
        for node in graph_data.get("nodes", []):
            node_id = node["id"]
            self.node_info[node_id] = node

        # 添加用户节点
        for user in users:
            user_id = user["id"]
            self.node_info[user_id] = {
                "id": user_id,
                "label": user["name"],
                "type": "user",
                "expertise": user.get("expertise", []),
                "interests": user.get("interests", [])
            }

        # 添加边
        for edge in graph_data.get("edges", []):
            source = edge["source"]
            target = edge["target"]
            edge_type = edge.get("type", "related")

            self.graph[source].append({
                "target": target,
                "type": edge_type,
                "weight": 1.0
            })

            # 无向图，添加反向边
            self.graph[target].append({
                "target": source,
                "type": edge_type,
                "weight": 1.0
            })

        # 根据用户兴趣添加用户-话题连接
        for user in users:
            user_id = user["id"]
            for topic in user.get("expertise", []):
                topic_id = f"topic_{topic}"
                if topic_id in self.node_info:
                    self.graph[user_id].append({
                        "target": topic_id,
                        "type": "expert_in",
                        "weight": 1.5
                    })
                    self.graph[topic_id].append({
                        "target": user_id,
                        "type": "expert",
                        "weight": 1.5
                    })

            for topic in user.get("interests", []):
                topic_id = f"topic_{topic}"
                if topic_id in self.node_info:
                    self.graph[user_id].append({
                        "target": topic_id,
                        "type": "interested_in",
                        "weight": 1.0
                    })

    def find_recommendations(
        self,
        topics: List[str],
        user_id: str,
        graph_data: Dict,
        users: List[Dict],
        posts: List[Dict],
        max_recommendations: int = 3
    ) -> List[Dict]:
        """
        基于话题找推荐

        返回推荐列表，每个推荐包含：
        - path: 推荐路径
        - target: 推荐目标（用户或资源）
        - explanation: 推荐解释
        - color: 显示颜色
        """

        # 构建图
        self.build_graph(graph_data, users, posts)

        recommendations = []

        # 为每个话题找推荐路径
        for topic in topics[:2]:  # 只处理前2个话题，避免太多
            topic_id = f"topic_{topic}"

            if topic_id not in self.node_info:
                continue

            # 查找与这个话题相关的专家
            paths = self._find_paths_to_experts(topic_id, max_depth=3)

            for path, expert_id in paths[:2]:
                expert_info = self.node_info.get(expert_id, {})

                recommendations.append({
                    "path": self._path_to_labels(path),
                    "path_ids": path,
                    "target": expert_info.get("label", expert_id),
                    "target_id": expert_id,
                    "explanation": f"通过{topic}找到相关专家",
                    "color": "#00D9FF",
                    "rec_type": "expert"
                })

            # 查找相关话题
            related_paths = self._find_related_topics(topic_id, max_depth=2)

            for path, related_id in related_paths[:1]:
                related_info = self.node_info.get(related_id, {})

                recommendations.append({
                    "path": self._path_to_labels(path),
                    "path_ids": path,
                    "target": related_info.get("label", related_id),
                    "target_id": related_id,
                    "explanation": f"与{topic}相关的话题",
                    "color": "#4ECDC4",
                    "rec_type": "topic"
                })

        # 限制推荐数量
        return recommendations[:max_recommendations]

    def find_counter_recommendations(
        self,
        user_id: str,
        graph_data: Dict,
        users: List[Dict],
        posts: List[Dict],
        max_recommendations: int = 3
    ) -> List[Dict]:
        """
        反向推荐：打破信息茧房

        找到与用户当前兴趣"不同但有意义关联"的内容
        """

        # 构建图
        self.build_graph(graph_data, users, posts)

        # 获取用户当前的兴趣聚类
        user_topics = self._get_user_cluster(user_id)

        if not user_topics:
            return []

        recommendations = []

        # 找到聚类外但有连接的话题
        all_topics = [nid for nid in self.node_info if self.node_info[nid]["type"] == "topic"]

        for topic_id in all_topics:
            if topic_id in user_topics:
                continue  # 跳过用户已关注的话题

            # 查找从用户话题到这个新话题的路径
            paths = self._find_cross_domain_paths(user_topics, topic_id, max_depth=4)

            if paths:
                path, _ = paths[0]
                topic_info = self.node_info.get(topic_id, {})

                # 检查是否是跨域推荐
                is_cross_domain = topic_info.get("cross_domain", False)

                recommendations.append({
                    "path": self._path_to_labels(path),
                    "path_ids": path,
                    "target": topic_info.get("label", topic_id),
                    "target_id": topic_id,
                    "explanation": "打破信息茧房的推荐" if is_cross_domain else "相关但未关注的话题",
                    "color": "#FF00FF" if is_cross_domain else "#FFA500",
                    "rec_type": "counter",
                    "is_cross_domain": is_cross_domain
                })

        # 优先返回跨域推荐
        recommendations.sort(key=lambda x: x.get("is_cross_domain", False), reverse=True)

        return recommendations[:max_recommendations]

    def _find_paths_to_experts(self, start_id: str, max_depth: int = 3) -> List[Tuple[List[str], str]]:
        """从话题找到专家的路径"""

        paths = []
        visited = set()
        queue = deque([(start_id, [start_id])])

        while queue:
            current, path = queue.popleft()

            if len(path) > max_depth:
                continue

            if current in visited:
                continue

            visited.add(current)

            # 检查是否是专家用户
            if current != start_id and self.node_info.get(current, {}).get("type") == "user":
                paths.append((path, current))
                if len(paths) >= 5:
                    break
                continue

            # 继续搜索
            for neighbor in self.graph.get(current, []):
                target = neighbor["target"]
                if target not in visited:
                    queue.append((target, path + [target]))

        return paths

    def _find_related_topics(self, start_id: str, max_depth: int = 2) -> List[Tuple[List[str], str]]:
        """找相关话题"""

        paths = []
        visited = set()
        queue = deque([(start_id, [start_id])])

        while queue:
            current, path = queue.popleft()

            if len(path) > max_depth:
                continue

            if current in visited:
                continue

            visited.add(current)

            # 检查是否是话题
            if current != start_id and self.node_info.get(current, {}).get("type") == "topic":
                paths.append((path, current))
                if len(paths) >= 3:
                    break
                continue

            # 继续搜索
            for neighbor in self.graph.get(current, []):
                target = neighbor["target"]
                if target not in visited:
                    queue.append((target, path + [target]))

        return paths

    def _get_user_cluster(self, user_id: str) -> Set[str]:
        """获取用户的兴趣聚类"""

        cluster = set()
        visited = set()
        queue = deque([user_id])

        while queue:
            current = queue.popleft()

            if current in visited:
                continue

            visited.add(current)

            if self.node_info.get(current, {}).get("type") == "topic":
                cluster.add(current)

            # 只扩展1跳
            if current == user_id:
                for neighbor in self.graph.get(current, []):
                    target = neighbor["target"]
                    if target not in visited:
                        queue.append(target)

        return cluster

    def _find_cross_domain_paths(
        self,
        start_cluster: Set[str],
        target_id: str,
        max_depth: int = 4
    ) -> List[Tuple[List[str], str]]:
        """找跨域路径"""

        paths = []

        for start_id in list(start_cluster)[:3]:  # 只从前3个起点搜索
            visited = set()
            queue = deque([(start_id, [start_id])])

            while queue:
                current, path = queue.popleft()

                if len(path) > max_depth:
                    continue

                if current in visited:
                    continue

                visited.add(current)

                if current == target_id:
                    paths.append((path, target_id))
                    break

                # 继续搜索
                for neighbor in self.graph.get(current, []):
                    next_node = neighbor["target"]
                    if next_node not in visited:
                        queue.append((next_node, path + [next_node]))

            if paths:
                break

        return paths

    def _path_to_labels(self, path: List[str]) -> List[str]:
        """将节点ID路径转换为标签路径"""
        return [self.node_info.get(node_id, {}).get("label", node_id) for node_id in path]
